package com.xaicode.algorithm.leetcode._101_200;

import java.util.Arrays;

/**
 * <a href="https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv">买卖股票的最佳时机4</a>
 *
 * <p>给定一个整数数组 <code>prices</code> ，它的第<em> </em><code>i</code> 个元素 <code>prices[i]</code> 是一支给定的股票在第 <code>i</code><em> </em>天的价格。</p>
 *
 * <p>设计一个算法来计算你所能获取的最大利润。你最多可以完成 <strong>k</strong> 笔交易。</p>
 *
 * <p><strong>注意：</strong>你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。</p>
 *
 * <p> </p>
 *
 * <p><strong>示例 1：</strong></p>
 *
 * <pre>
 * <strong>输入：</strong>k = 2, prices = [2,4,1]
 * <strong>输出：</strong>2
 * <strong>解释：</strong>在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。</pre>
 *
 * <p><strong>示例 2：</strong></p>
 *
 * <pre>
 * <strong>输入：</strong>k = 2, prices = [3,2,6,5,0,3]
 * <strong>输出：</strong>7
 * <strong>解释：</strong>在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
 *      随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。</pre>
 *
 * <p> </p>
 *
 * <p><strong>提示：</strong></p>
 *
 * <ul>
 * 	<li><code>0 <= k <= 100</code></li>
 * 	<li><code>0 <= prices.length <= 1000</code></li>
 * 	<li><code>0 <= prices[i] <= 1000</code></li>
 * </ul>
 *
 * @author beborn xaicode@sina.com
 */
public class _188_Hard_BestTimeToBuyAndSellStock4 {

    public static void main(String[] args) {
        _188_Hard_BestTimeToBuyAndSellStock4 stock4 = new _188_Hard_BestTimeToBuyAndSellStock4();

        int[] prices = new int[]{4, 2, 7, 1, 2, 5};
        int maxProfit = stock4.maxProfit2(4, prices);
        System.out.println(maxProfit);
    }

    /**
     * 动态规划
     * <p>
     * 交易次数：由于只有先买入再卖出才能获得最大收益（无操作情况除外），最大交易次数为 n/2
     * <p>
     * 执行耗时:8 ms,击败了43.35% 的Java用户
     * 内存消耗:38.1 MB,击败了36.26% 的Java用户
     * <p>
     * 时间复杂度：O(n*min(n,k))，其中 n 是数组 prices 的大小，即我们使用二重循环进行动态规划需要的时间。
     * <p>
     * 空间复杂度：O(n*min(n,k)) 或 O(min(n,k))，取决于我们使用二维数组还是一维数组进行动态规划。
     *
     * @param k      max trading count
     * @param prices price daily
     * @return max profit
     */
    public int maxProfit(int k, int[] prices) {
        if (prices.length == 0) {
            return 0;
        }

        int n = prices.length;
        // max trading count actually
        k = Math.min(k, n / 2);
        // the nth day has k+1 times trading, and has one stock
        int[][] buy = new int[n][k + 1];
        // the nth day has k+1 times trading, and sell the stock remaining
        int[][] sell = new int[n][k + 1];

        // the first day with buying a stock
        buy[0][0] = -prices[0];
        // the first will do nth. cause no remaining stock
        sell[0][0] = 0;
        // set a small value to the trading profit of first day
        for (int i = 1; i <= k; ++i) {
            buy[0][i] = sell[0][i] = Integer.MIN_VALUE / 2;
        }
        System.out.printf("the 1th day: \n\tbuy[0][0]=%d\n\tsell[0][0]=%d", buy[0][0], sell[0][0]);

        // start from the second day
        for (int i = 1; i < n; ++i) {
            // the 'buy' on the (i)th day
            // buy[i-1][0]: do nth. on the (i-1)th day
            // sell[i-1][0]-prices[i]: buy a stock today
            buy[i][0] = Math.max(buy[i - 1][0], sell[i - 1][0] - prices[i]);
            System.out.printf("\nthe %d day: buy[%d][0]", i, i);
            for (int j = 1; j <= k; ++j) {
                buy[i][j] = Math.max(buy[i - 1][j], sell[i - 1][j] - prices[i]);
                System.out.printf("\nthe %dth day:", i);
                System.out.printf("\n\tbuy[%d][%d]=Max(%d, %d)",
                        i, j, buy[i - 1][j], sell[i - 1][j] - prices[i]);
                sell[i][j] = Math.max(sell[i - 1][j], buy[i - 1][j - 1] + prices[i]);
                System.out.printf("\n\tsell[%d][%d]=Max(%d, %d)",
                        i, j, sell[i - 1][j], buy[i - 1][j - 1] + prices[i]);
            }
            System.out.println("\n-------------");
        }

        int theMaxProfit = Arrays.stream(sell[n - 1]).max().getAsInt();
        System.out.printf("\nafter compute, the max profit is in sell[%d]=%s, is %d",
                n - 1, Arrays.toString(sell[n - 1]), theMaxProfit);
        return theMaxProfit;
    }

    public int maxProfit2(int k, int[] prices) {
        if (prices.length == 0) {
            return 0;
        }

        int n = prices.length;
        k = Math.min(k, n / 2);
        int[] buy = new int[k + 1];
        int[] sell = new int[k + 1];

        buy[0] = -prices[0];
        sell[0] = 0;
        for (int i = 1; i <= k; ++i) {
            buy[i] = sell[i] = Integer.MIN_VALUE / 2;
        }

        for (int i = 1; i < n; ++i) {
            buy[0] = Math.max(buy[0], sell[0] - prices[i]);
            for (int j = 1; j <= k; ++j) {
                buy[j] = Math.max(buy[j], sell[j] - prices[i]);
                sell[j] = Math.max(sell[j], buy[j - 1] + prices[i]);
            }
        }

        return Arrays.stream(sell).max().getAsInt();
    }
}
